본문으로 건너뛰기

그래프 탐색 (BFS, DFS)

그래프란?​

그래프는 점(정점)과 선(간선)으로 이루어진 자료구조입니다.

마치 지하철 노선도나 친구 관계도와 같습니다.

  • 정점(Vertex): 지하철역, 사람
  • 간선(Edge): 지하철 노선, 친구 관계
친구 관계 예시:
    A --- B
    |     |
    |     |
    C --- D

A는 B, C와 친구
B는 A, D와 친구
C는 A, D와 친구  
D는 B, C와 친구

그래프 표현 방법​

인접 리스트​

// 가장 많이 사용하는 방법
const graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
};

// 또는 배열로
const graphArray = [
    [1, 2],     // 0번 노드는 1, 2와 연결
    [0, 3],     // 1번 노드는 0, 3과 연결
    [0, 3],     // 2번 노드는 0, 3과 연결
    [1, 2]      // 3번 노드는 1, 2와 연결
];

인접 행렬​

// 메모리를 더 많이 사용하지만 연결 확인이 빠름
const adjacencyMatrix = [
    [0, 1, 1, 0],  // A와 연결된 노드들
    [1, 0, 0, 1],  // B와 연결된 노드들
    [1, 0, 0, 1],  // C와 연결된 노드들
    [0, 1, 1, 0]   // D와 연결된 노드들
];

성능 비교​

function compareGraphRepresentation() {
    const n = 1000; // 노드 수
    const edges = 5000; // 간선 수
    
    // 인접 리스트 생성
    const adjList = Array(n).fill().map(() => []);
    for (let i = 0; i < edges; i++) {
        const from = Math.floor(Math.random() * n);
        const to = Math.floor(Math.random() * n);
        if (from !== to) {
            adjList[from].push(to);
            adjList[to].push(from);
        }
    }
    
    // 인접 행렬 생성
    const adjMatrix = Array(n).fill().map(() => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let neighbor of adjList[i]) {
            adjMatrix[i][neighbor] = 1;
        }
    }
    
    // 연결 확인 성능 테스트
    let start = performance.now();
    for (let i = 0; i < 10000; i++) {
        const from = Math.floor(Math.random() * n);
        const to = Math.floor(Math.random() * n);
        // 인접 리스트에서 연결 확인
        adjList[from].includes(to);
    }
    let end = performance.now();
    const listTime = end - start;
    
    start = performance.now();
    for (let i = 0; i < 10000; i++) {
        const from = Math.floor(Math.random() * n);
        const to = Math.floor(Math.random() * n);
        // 인접 행렬에서 연결 확인
        adjMatrix[from][to] === 1;
    }
    end = performance.now();
    const matrixTime = end - start;
    
    console.log(`인접 리스트: ${listTime.toFixed(2)}ms`);
    console.log(`인접 행렬: ${matrixTime.toFixed(2)}ms`);
    
    console.log(`\n메모리 사용량 (대략):`);
    console.log(`인접 리스트: ${edges * 2 * 4}bytes`); // 간선당 2개 참조, 4바이트씩
    console.log(`인접 행렬: ${n * n * 4}bytes`); // n×n 행렬, 4바이트씩
}

희소 그래프에서는 인접 리스트가, 밀집 그래프에서는 인접 행렬이 유리합니다

너비 우선 탐색 (BFS)​

BFS는 가까운 노드부터 차례대로 탐색하는 방법입니다.

기본 구현​

function bfs(graph, start) {
    const visited = new Set();
    const queue = [start];
    const result = [];
    
    visited.add(start);
    
    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node);
        
        for (let neighbor of graph[node] || []) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    
    return result;
}

const graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
};

console.log(bfs(graph, 'A')); // ['A', 'B', 'C', 'D', 'E', 'F']

최단 거리 찾기​

function shortestPath(graph, start, end) {
    const visited = new Set();
    const queue = [[start, [start]]]; // [현재노드, 경로]
    
    visited.add(start);
    
    while (queue.length > 0) {
        const [node, path] = queue.shift();
        
        if (node === end) {
            return path;
        }
        
        for (let neighbor of graph[node] || []) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([neighbor, [...path, neighbor]]);
            }
        }
    }
    
    return null; // 경로가 없음
}

console.log(shortestPath(graph, 'A', 'F')); // ['A', 'C', 'F']

레벨별 탐색​

function bfsLevels(graph, start) {
    const visited = new Set();
    let currentLevel = [start];
    const levels = [];
    
    visited.add(start);
    
    while (currentLevel.length > 0) {
        levels.push([...currentLevel]);
        const nextLevel = [];
        
        for (let node of currentLevel) {
            for (let neighbor of graph[node] || []) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    nextLevel.push(neighbor);
                }
            }
        }
        
        currentLevel = nextLevel;
    }
    
    return levels;
}

console.log(bfsLevels(graph, 'A'));
// [['A'], ['B', 'C'], ['D', 'E', 'F']]

깊이 우선 탐색 (DFS)​

DFS는 한 방향으로 끝까지 가본 후 되돌아가는 방법입니다.

재귀 구현​

function dfsRecursive(graph, start, visited = new Set(), result = []) {
    visited.add(start);
    result.push(start);
    
    for (let neighbor of graph[start] || []) {
        if (!visited.has(neighbor)) {
            dfsRecursive(graph, neighbor, visited, result);
        }
    }
    
    return result;
}

console.log(dfsRecursive(graph, 'A')); // ['A', 'B', 'D', 'E', 'F', 'C']

반복문 구현​

function dfsIterative(graph, start) {
    const visited = new Set();
    const stack = [start];
    const result = [];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        if (!visited.has(node)) {
            visited.add(node);
            result.push(node);
            
            // 역순으로 추가 (재귀와 같은 순서를 위해)
            for (let i = (graph[node] || []).length - 1; i >= 0; i--) {
                const neighbor = graph[node][i];
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
    
    return result;
}

console.log(dfsIterative(graph, 'A'));

경로 찾기​

function findAllPaths(graph, start, end, path = [], visited = new Set()) {
    path = [...path, start];
    visited = new Set([...visited, start]);
    
    if (start === end) {
        return [path];
    }
    
    const paths = [];
    for (let neighbor of graph[start] || []) {
        if (!visited.has(neighbor)) {
            const newPaths = findAllPaths(graph, neighbor, end, path, visited);
            paths.push(...newPaths);
        }
    }
    
    return paths;
}

console.log(findAllPaths(graph, 'A', 'F'));
// [['A', 'B', 'E', 'F'], ['A', 'C', 'F']]

BFS vs DFS 성능 비교​

function compareBfsDfs() {
    // 큰 그래프 생성
    const n = 10000;
    const largeGraph = {};
    
    for (let i = 0; i < n; i++) {
        largeGraph[i] = [];
        // 각 노드를 최대 10개의 다른 노드와 연결
        for (let j = 0; j < 10; j++) {
            const neighbor = Math.floor(Math.random() * n);
            if (neighbor !== i && !largeGraph[i].includes(neighbor)) {
                largeGraph[i].push(neighbor);
            }
        }
    }
    
    const start = 0;
    
    // BFS 성능 테스트
    let startTime = performance.now();
    bfs(largeGraph, start);
    let endTime = performance.now();
    const bfsTime = endTime - startTime;
    
    // DFS 성능 테스트
    startTime = performance.now();
    dfsIterative(largeGraph, start);
    endTime = performance.now();
    const dfsTime = endTime - startTime;
    
    console.log(`BFS: ${bfsTime.toFixed(2)}ms`);
    console.log(`DFS: ${dfsTime.toFixed(2)}ms`);
    
    // 메모리 사용량 차이
    console.log(`\n메모리 사용 특성:`);
    console.log(`BFS: 큐 사용 - 너비에 비례`);
    console.log(`DFS: 스택 사용 - 깊이에 비례`);
}

일반적으로 DFS가 약간 빠르지만, 메모리 사용 패턴이 다릅니다

실제 문제 응용​

섬의 개수 세기​

function numIslands(grid) {
    if (!grid || grid.length === 0) return 0;
    
    const rows = grid.length;
    const cols = grid[0].length;
    let count = 0;
    
    function dfs(r, c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') {
            return;
        }
        
        grid[r][c] = '0'; // 방문 표시
        
        // 상하좌우 탐색
        dfs(r - 1, c);
        dfs(r + 1, c);
        dfs(r, c - 1);
        dfs(r, c + 1);
    }
    
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') {
                count++;
                dfs(r, c);
            }
        }
    }
    
    return count;
}

const grid = [
    ['1','1','1','1','0'],
    ['1','1','0','1','0'],
    ['1','1','0','0','0'],
    ['0','0','0','0','0']
];
console.log(numIslands(grid)); // 1

미로 탈출​

function solveMaze(maze, start, end) {
    const rows = maze.length;
    const cols = maze[0].length;
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
    function bfs() {
        const queue = [[start[0], start[1], 0]]; // [row, col, distance]
        const visited = new Set();
        visited.add(`${start[0]},${start[1]}`);
        
        while (queue.length > 0) {
            const [r, c, dist] = queue.shift();
            
            if (r === end[0] && c === end[1]) {
                return dist;
            }
            
            for (let [dr, dc] of directions) {
                const nr = r + dr;
                const nc = c + dc;
                const key = `${nr},${nc}`;
                
                if (nr >= 0 && nr < rows && 
                    nc >= 0 && nc < cols && 
                    maze[nr][nc] === 0 && 
                    !visited.has(key)) {
                    
                    visited.add(key);
                    queue.push([nr, nc, dist + 1]);
                }
            }
        }
        
        return -1; // 경로 없음
    }
    
    return bfs();
}

const maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0]
];

console.log(solveMaze(maze, [0, 0], [4, 4])); // 8

위상 정렬​

function topologicalSort(graph, nodes) {
    const inDegree = {};
    const result = [];
    const queue = [];
    
    // 진입 차수 계산
    for (let node of nodes) {
        inDegree[node] = 0;
    }
    
    for (let node of nodes) {
        for (let neighbor of graph[node] || []) {
            inDegree[neighbor]++;
        }
    }
    
    // 진입 차수가 0인 노드들을 큐에 추가
    for (let node of nodes) {
        if (inDegree[node] === 0) {
            queue.push(node);
        }
    }
    
    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node);
        
        for (let neighbor of graph[node] || []) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }
    
    return result.length === nodes.length ? result : null; // 사이클 있으면 null
}

const courseGraph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
};
const courses = ['A', 'B', 'C', 'D'];
console.log(topologicalSort(courseGraph, courses)); // ['A', 'B', 'C', 'D'] 또는 ['A', 'C', 'B', 'D']

사이클 감지​

function hasCycle(graph, nodes) {
    const WHITE = 0, GRAY = 1, BLACK = 2;
    const colors = {};
    
    // 모든 노드를 WHITE로 초기화
    for (let node of nodes) {
        colors[node] = WHITE;
    }
    
    function dfs(node) {
        colors[node] = GRAY;
        
        for (let neighbor of graph[node] || []) {
            if (colors[neighbor] === GRAY) {
                return true; // 백엣지 발견 (사이클)
            }
            if (colors[neighbor] === WHITE && dfs(neighbor)) {
                return true;
            }
        }
        
        colors[node] = BLACK;
        return false;
    }
    
    for (let node of nodes) {
        if (colors[node] === WHITE) {
            if (dfs(node)) {
                return true;
            }
        }
    }
    
    return false;
}

const cyclicGraph = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A']  // 사이클!
};
console.log(hasCycle(cyclicGraph, ['A', 'B', 'C'])); // true

그래프 탐색 최적화​

양방향 BFS​

function bidirectionalBFS(graph, start, end) {
    if (start === end) return [start];
    
    const visitedFromStart = new Map();
    const visitedFromEnd = new Map();
    const queueStart = [start];
    const queueEnd = [end];
    
    visitedFromStart.set(start, [start]);
    visitedFromEnd.set(end, [end]);
    
    while (queueStart.length > 0 || queueEnd.length > 0) {
        // 앞에서부터 탐색
        if (queueStart.length > 0) {
            const node = queueStart.shift();
            
            for (let neighbor of graph[node] || []) {
                if (visitedFromEnd.has(neighbor)) {
                    // 만남! 경로 합치기
                    const pathFromStart = visitedFromStart.get(node);
                    const pathFromEnd = visitedFromEnd.get(neighbor);
                    return [...pathFromStart, ...pathFromEnd.slice().reverse()];
                }
                
                if (!visitedFromStart.has(neighbor)) {
                    visitedFromStart.set(neighbor, [...visitedFromStart.get(node), neighbor]);
                    queueStart.push(neighbor);
                }
            }
        }
        
        // 뒤에서부터 탐색
        if (queueEnd.length > 0) {
            const node = queueEnd.shift();
            
            for (let neighbor of graph[node] || []) {
                if (visitedFromStart.has(neighbor)) {
                    // 만남! 경로 합치기
                    const pathFromStart = visitedFromStart.get(neighbor);
                    const pathFromEnd = visitedFromEnd.get(node);
                    return [...pathFromStart, ...pathFromEnd.slice().reverse()];
                }
                
                if (!visitedFromEnd.has(neighbor)) {
                    visitedFromEnd.set(neighbor, [neighbor, ...visitedFromEnd.get(node)]);
                    queueEnd.push(neighbor);
                }
            }
        }
    }
    
    return null; // 경로 없음
}

언제 어떤 탐색을 사용하나요?​

BFS 사용 시기​

  • 최단 경로를 찾을 때
  • 레벨별로 탐색할 때
  • 가까운 노드부터 확인하고 싶을 때
  • 메모리가 충분할 때

DFS 사용 시기​

  • 모든 경로를 탐색할 때
  • 깊은 해답을 찾을 때
  • 메모리를 절약하고 싶을 때
  • 백트래킹이 필요할 때
function chooseSearchMethod() {
    console.log("탐색 방법 선택 가이드:");
    console.log("\nBFS 사용:");
    console.log("- 최단 거리/경로 문제");
    console.log("- 레벨 순서 탐색");
    console.log("- 가까운 것부터 찾기");
    
    console.log("\nDFS 사용:");
    console.log("- 모든 경우 탐색");
    console.log("- 깊이 우선 탐색");
    console.log("- 백트래킹 문제");
    console.log("- 사이클 감지");
}

그래프 탐색은 많은 실제 문제에서 활용되는 핵심 알고리즘입니다. BFS와 DFS의 특성을 이해하고 상황에 맞게 선택하는 것이 중요합니다.